/*
* 基数排序：
* 基数排序也是一个分布式排序算法，它根据数字的有效位或者基数将整数分布到桶中。基数是基于数组中值得计数制的。
* 比如，对于十进制数，使用的基数是10。因此，算法将会使用10个桶来分布元素并且首先基于个位数字进行排序，然后基于十位数字，然后基于百位数字，以此类推。
*
* */
function radixSort(arr,radixBase = 10){ //数组 进制
    if(arr.length < 2){
        return arr
    }
    let minValue = arr[0] //初始化最大值
    let maxValue = arr[0] //初始化最小值
    for(let index = 1; index < arr.length; index++){
        if(arr[index] > maxValue){ //如果循环到的元素比初始最大值还要大
            maxValue = arr[index] //就更新最大值
        }else if(arr[index] < minValue){ //如果循环到到元素比初始最小值还小
            minValue = arr[index] //就更新最小值
        }
    }
    let significantDigi = 1 //基准数字
    while((maxValue - minValue) / significantDigi >= 1){
        arr = countingSort(arr,radixBase,significantDigi,minValue)
        significantDigi *= radixBase //基准数字×进制
    }
    return arr
}
function countingSort(arr,radixBase,significantDigi,minValue){
    let bucketsIndex
    let buckets = [] //桶，用来装同一类数，个位数1装一桶，个位数2装一桶，个位数3装一桶...（注意0比9大，因为10>9）
    let aux = [] //定义辅助数组

    for(let index = 0; index < radixBase; index++){ //for循环初始化buckets数组
        buckets[index] = 0 //先给桶计数
    }

    for(let index = 0; index < arr.length; index++){
        bucketsIndex = Math.floor(((arr[index] - minValue) / significantDigi) % radixBase) //找出桶的下标
        buckets[bucketsIndex]++ //对应的桶计数++
    }

    for(let index = 1; index < radixBase; index++){ //for循环初始化buckets数组
        buckets[index] += buckets[index - 1] //数据来进行累加
    }

    for(let i = arr.length - 1; i >= 0; i--){
        bucketsIndex = Math.floor(((arr[i] - minValue) / significantDigi) % radixBase) //找出桶的下标
        aux[--buckets[bucketsIndex]] = arr[i]
    }

    for(let index = 0; index < arr.length; index++){
        arr[index] = aux[index]
    }

    return arr
}

let arr = [1,5,6,4,8,94,24,63,45,2]
radixSort(arr)